package com.kaifamiao.month03.day0310;

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] searchArray = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        // 二分查找递归实现
        int indexRecursion = binarySearchRecursion(searchArray,0,searchArray.length,30);
        System.out.println(indexRecursion);
        // 二分查找普通实现
        int indexOrdinary = binarySearchOrdinary(searchArray,30);
        System.out.println(indexOrdinary);

    }

    /**
     * 二分查找递归实现
     * @param searchArray 有序数组
     * @param start 开始位置
     * @param end 结束位置
     * @param key 查找元素
     * @return key的数组下标，没有返回-1
     */
    public static int binarySearchRecursion(int[] searchArray, int start, int end, int key){
        int mid = (end - start) / 2 + start;
        if (searchArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > searchArray[mid]) {
            return binarySearchRecursion(searchArray, mid + 1, end, key);
        } else if (key < searchArray[mid]) {
            return binarySearchRecursion(searchArray, start, mid - 1, key);
        }
        return -1;
    }

    /**
     * 二分查找普通实现
     * @param searchArray
     * @param key
     * @return
     */
    public static int binarySearchOrdinary(int[] searchArray, int key){
        int mid = searchArray.length / 2;
        if (key == searchArray[mid]) {
            return mid;
        }
        int start = 0;
        int end = searchArray.length - 1;
        while (start <= end) {
            mid = (end - start) / 2 + start;
            if (key < searchArray[mid]) {
                end = mid - 1;
            } else if (key > searchArray[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
